/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class MaximumSubarray {

	int max;

	public int[] search(int[] A, int l, int r) {
		if (l == r) {
			max = Math.max(max, A[l]);
			return new int[] { A[l], A[l], A[l] };
		}
		int[] val = new int[3];
		int mid = l + r >> 1;
		int[] lval = search(A, l, mid);
		int[] rval = search(A, mid + 1, r);
		val[2] = lval[2] + rval[2];
		val[0] = Math.max(lval[0], lval[2] + rval[0]);
		val[1] = Math.max(rval[1], lval[1] + rval[2]);
		max = Math.max(max, lval[1]);
		max = Math.max(max, rval[0]);
		max = Math.max(max, lval[1] + rval[0]);
		return val;
	}

	public int maxSubArray(int[] A) {
		int n = A.length;
		max = Integer.MIN_VALUE;
		search(A, 0, n - 1);
		return max;
	}

	public int maxSubArrayNaive(int[] A) {
		int n = A.length;
		int max = Integer.MIN_VALUE, sum = 0;
		for (int i = 0; i < n; ++i) {
			sum += A[i];
			max = Math.max(max, sum);
			if (sum < 0)
				sum = 0;
		}
		return max;
	}

	public static void main(String[] args) {
		MaximumSubarray a = new MaximumSubarray();
		System.out.println(a.maxSubArray(new int[] { -1, 2, -1, 4 }));
	}
}
